package dp;

public class dp4 {


    public static void main(String[] args) {
        int []nums={-3,-2,-3};
        System.out.println(maxSubarraySumCircular(nums));
    }


    public static int maxSubarraySumCircular(int[] nums) {

        int n=nums.length;
        if(n==1)return nums[0];
        int []dp1=new int[n];
        int []dp2=new int[n];
        dp1[0]=nums[0];
        dp2[0]=nums[0];
        int min=Integer.MAX_VALUE;
        int max=Integer.MIN_VALUE;
        int sum=nums[0];
        for(int i=1;i<n;i++){
            sum+=nums[i];
            dp1[i]=Math.max(dp1[i-1]+nums[i],nums[i]);
            dp2[i]=Math.min(dp2[i-1]+nums[i],nums[i]);
            min=Math.min(dp2[i],min);
            max=Math.max(dp1[i],max);
        }
        if(sum==min)return max;
        return Math.max(max,sum-min);
    }


    public int maxSubArray(int[] nums) {
        int n=nums.length;
        int []dp=new int[n];
        dp[0]=nums[0];
        for(int i=1;i<n;i++){
            dp[i]=Math.max(nums[i],nums[i]+dp[i-1]);
        }
        int ret=Integer.MIN_VALUE;
        for(int i=0;i<n;i++)ret=Math.max(ret,dp[i]);
        return ret;
    }

    public int maxProfit(int k, int[] prices) {
        int INF=0x3f3f3f3f;
        int n=prices.length;

        int [][]f=new int[n][k+1];
        int [][]g=new int[n][k+1];
        for(int i=0;i<=k;i++)f[0][i]=g[0][i]=-INF;
        f[0][0]=-prices[0];
        g[0][0]=0;

        for(int i=1;i<n;i++){
            for(int j=0;j<=k;j++){
                f[i][j]=Math.max(f[i-1][j],g[i-1][j]-prices[i]);
                g[i][j]=g[i-1][j];
                if(j-1>=0)g[i][j]=Math.max(g[i-1][j],f[i-1][j-1]+prices[i]);
            }
        }
        int ret=-INF;
        for(int i=0;i<=k;i++)ret=Math.max(g[n-1][i],ret);
        return ret;
    }

    public int maxProfit(int[] prices) {
        int INF=0x3f3f3f3f;
        int n=prices.length;
        int [][]f=new int[n][3];
        int [][]g=new int[n][3];
        f[0][1]=f[0][2]=g[0][1]=g[0][2]=-INF;
        f[0][0]=-prices[0];
        g[0][0]=0;

        for(int i=1;i<n;i++){
            for(int j=0;j<3;j++){
                f[i][j]=Math.max(f[i-1][j],g[i-1][j]-prices[i]);
                g[i][j]=g[i-1][j];
                if(j-1>=0)g[i][j]=Math.max(g[i-1][j],f[i-1][j-1]+prices[i]);
            }
        }

        return Math.max(Math.max(g[n-1][0],g[n-1][1]),g[n-1][2]);

    }
}
